package com.solming.leetcode.question;

public class NumMatrix304 {

    int[][] numMatrixArr = null;

    public NumMatrix304(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        numMatrixArr = new int[m][n + 1];
        for (int i = 0; i < m; i++) {
            numMatrixArr[i][0] = 0;
        }
        for (int i = 0; i < m; i++) {

            for (int j = 0; j < n; j++) {
                numMatrixArr[i][j + 1] = numMatrixArr[i][j] + matrix[i][j];
            }
        }

    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int min = Math.min(row1, row2);
        int max = Math.max(row1, row2);

        int minCol = Math.min(col1, col2);
        int maxCol = Math.max(col1, col2);

        int sum = 0;
        for (; min <= max; min++) {
            sum += numMatrixArr[min][maxCol + 1] - numMatrixArr[min][minCol];
        }
        return sum;

    }

    public static void main(String[] args) {
        int[][] matrix = new int[][]{
                {3, 0, 1, 4, 2},
                {5, 6, 3, 2, 1},
                {1, 2, 0, 1, 5},
                {4, 1, 0, 1, 7},
                {1, 0, 3, 0, 5},
        };
        System.out.println(new NumMatrix304(matrix).sumRegion(2, 1, 4, 3));



    }


}
